package leetcode.day_2020_12_14_12_21;

import java.util.HashMap;
import java.util.Map;

/**
 * 337. 打家劫舍 III
 */
public class L_337 {
    static Map<TreeNode, Integer> map = new HashMap<>();
    public static void main(String[] args) {
        TreeNode root = new TreeNode(-1);
        int[] res = dp(root);
        Math.max(res[0], res[1]);
    }

    public static int rob(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if(map.containsKey(root)) {
            return map.get(root);
        }
        // 抢
        int do_it = root.val + (root.left == null ? 0 : rob(root.left.left) + rob(root.left.right))
                             + (root.right == null ? 0 :rob(root.right.left) + rob(root.right.right));
        // 不抢
        int not_do = rob(root.left) + rob(root.right);
        int res = Math.max(do_it, not_do);
        map.put(root, res);
        return res;
    }

    public static int[] dp(TreeNode root) {
        if (root == null) {
            return new int[]{0, 0};
        }
        int[] left = dp(root.left);
        int[] right = dp(root.right);
        // 抢
        int rob = root.val + left[0] + right[0];
        // 不抢
        int not_rob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return new int[]{not_rob, rob};
    }
}
